The field of the invention is computer-implemented genetic algorithms; more particularly, the present invention relates to automatically creating computer programs to solve problems using computer-implemented genetic algorithms, including embodiments that use automatically defined stores, loops, and recursions.
A central challenge of computer science is to get a computer to solve a complex problem without explicitly telling the computer how to do it (e.g., programming it). In particular, it would be desirable to have a problem-independent system whose input is a high-level statement of a problem""s requirements and whose output is a working computer program that solves the given problem.
Genetic programming is an automatic technique that is capable of creating complex designs and structures, such as computer programs. Genetic programming approaches a problem in terms of xe2x80x9cwhat needs to be donexe2x80x9d as opposed to xe2x80x9chow to do it.xe2x80x9d For example, genetic programming has demonstrated that it is capable of generating computer programs from a given problem definition. Genetic programming creates a variety of computer programs because it employs a probabilistic process of natural selection to evolve computer constructs and because it is unencumbered by the preconceptions that often channel human thinking down familiar paths.
Genetic Algorithms
A genetic algorithm provides a method of improving a given set of objects. The processes of natural selection and survival of the fittest provide a theoretical base for the genetic algorithm. In Adaptation in Artificial and Natural Systems (MIT Press 1975), Professor John H. Holland presents a mathematical theory of adaptation for both natural and artificial systems. An important part of Holland""s book describes a xe2x80x9cgenetic algorithmxe2x80x9d patterned after nature""s methods for biological adaptation. In a later work, Holland (1986) describes a classifier system that employs a genetic algorithm and a bucket brigade algorithm to solve problems. U.S. Pat. No. 4,697,242 (Holland et al.) and U.S. Pat. No. 4,881,178 (Holland et al.) describe classifier systems that use fixed length binary strings in conjunction with a genetic algorithm. The fixed length binary strings of a classifier represent IF-THEN rules.
Genetic Programming
xe2x80x9cGenetic programmingxe2x80x9d (also called the xe2x80x9cnon-linear genetic algorithmxe2x80x9d or the xe2x80x9chierarchical genetic algorithmxe2x80x9d in previous years) is described in the book entitled Genetic Programming: On the Programming of Computers by Means of Natural Selection, Koza, John R., Cambridge, Mass.: The MIT Press, 1992, the book entitled Genetic Programming II: Automatic Discovery of Reusable Programs, Koza, John R., Cambridge, Mass.: The MIT Press, 1994, and in U.S. Pat. Nos. 4,935,877, 5,136,686, 5,148,513, 5,343,554, 5,742,738, and 5,867,397.
Genetic programming is referred to as xe2x80x9cnon-linearxe2x80x9d or xe2x80x9chierarchicalxe2x80x9d because the original genetic algorithm described by Holland in 1975 operated on linear strings of characters (resembling chromosomes in nature), whereas genetic programming operates on hierarchical program trees of various sizes and shapes.
Genetic programming is capable of evolving computer programs that solve, or approximately solve, a variety of problems from a variety of fields. Genetic programming starts with a xe2x80x9cprimordial oozexe2x80x9d of randomly generated programs composed of the available programmatic ingredients and then applies the principles of animal husbandry to breed a new (and often improved) population of programs. Genetic programming performs the breeding in a domain-independent way using the Darwinian principle of survival of the fittest, an analog of the naturally-occurring genetic operation of crossover (sexual recombination), and occasional mutation. The crossover operation is designed to create syntactically valid offspring programs (given closure amongst the set of ingredients). Genetic programming combines the expressive high-level symbolic representations of computer programs with the near-optimal efficiency of improvement associated with Holland""s genetic algorithm. A program that solves (or approximately solves) a given problem often emerges from this process.
As demonstrated in the book, Genetic Programming II: Automatic Discovery of Reusable Programs Koza, John R., Cambridge, Mass.: The MIT Press, 1994, genetic programming can evolve multi-part programs consisting of a main program and one or more reusable, parameterized, hierarchically-called subprograms (called automatically defined functions or ADFs).
A basic embodiment of genetic programming breeds computer programs to solve problems by executing the following steps:
(1) Generate an initial population of random compositions of the functions and terminals of the problem (i.e., computer programs).
(2) Iteratively perform the following substeps until the termination criterion has been satisfied:
(A) Execute each program in the population and assign it a fitness value using the fitness measure.
(B) Create a new population of computer programs by applying the following operations. The operations are applied to computer program(s) chosen from the population with a probability based on fitness.
(i) Reproduction: Copy an existing program to the new population.
(ii) Crossover: Create new offspring program(s) for the new population by recombining randomly chosen parts of two existing programs.
(iii) Mutation: Create one new offspring program for the new population by randomly mutating a randomly chosen part of one existing program.
(3) The program that is identified by the method of result designation (e.g., the best-so-far individual) is designated as the result of the genetic algorithm for the run. This result may be a solution (or an approximate solution) to the problem.
Other genetic programming processes may use additional operations such as xe2x80x9cpermutation,xe2x80x9d xe2x80x9cdefine building blockxe2x80x9d (also called xe2x80x9cencapsulationxe2x80x9d), or the architecture-altering operations discussed below.
Before applying genetic programming to a problem, the user must perform five major preparatory steps, as shown in FIG. 1B. The preparatory steps of genetic programming are the user""s way of communicating the high-level statement of the problem to the genetic programming system. The preparatory steps identify what the user provides to the genetic programming system before launching a run of genetic programming. The preparatory steps serve to unmistakably distinguish between what the user supplies to the genetic programming system and what the system delivers.
In one embodiment, the five major preparatory steps for genetic programming entail determining: (1) the set of terminals (e.g., the actual variables of the problem, zero-argument functions, and random constants, if any) for each branch of the to-be-evolved computer program; (2) the set of primitive functions for each to-be-evolved branch; (3) the fitness measure (or other arrangement for explicitly or implicitly measuring fitness); (4) the parameters for controlling the run; and (5) the termination criterion and the method of result designation for the run. In addition, when automatically defined operations are used, the architecture of the programs to be evolved must be determined in some way (not shown). A traditional approach is for the user to specify the architecture prior to the run of genetic programming. In this approach, the user performs an architecture-defining preparatory step prior to the run of genetic programming. FIG. 1B shows the results 115 of the preparatory steps as input to genetic programming 105 to produce a computer program 110.
Before applying genetic programming to a problem, where a multi-part program is to be evolved, it is the user""s responsibility to specify the architecture of the computer program. In one embodiment, the architecture of a computer program consists of the number of result-producing branches (which is just one for a one-output program), the number of function-defining branches with the number or arguments possessed by each function-defining branch (subroutine, automatically defined function), the number of loop-defining branches with associated arguments, the number of recursion-defining branches with associated arguments, and the amount and type of storage available to the program. Many programs consist of just one result-producing branch and no other branches. Determining the architecture for an overall program may facilitate or frustrate evolution of the solution to the problem. For example, a 6-dimensional problem may have a natural decomposition into 3-dimensional subproblems. If 3-dimensional subprograms are readily available during the evolutionary process, the problem may be relatively easy to solve by means of the evolutionary process; however, if they are not available, the problem may be difficult or impossible to solve. Thus, the question arises as to how to determine the architecture of the programs that participate in the evolutionary process.
The existing methods for making these architectural choices include the methods of prospective analysis of the nature of the problem, seemingly sufficient capacity, affordable capacity, and retrospective analysis of the results of actual runs. Sometimes these architectural choices flow directly from the nature of the problem that they are virtually mandated. However, in general, there is not way of knowing a priori the architecture of the program corresponding to the solution the problem.
Some problems have a known decomposition involving subproblems of known dimensionality. For example, some problems involve finding a computer program (e.g., mathematical expression, composition of primitive functions and terminals) that produces the observed value of a dependent variable as its output when given the values of a certain number of independent variables as input. Problems of this type are called problems of symbolic regression, system identification, or simply xe2x80x9cblack boxxe2x80x9d problems. In many instances, it may be known that a certain number of the independent variables represent a certain subsystem or subspace. In that event, the problem may be decomposable into subproblems based on the known lower dimensionality of the known subsystem or subspace.
For many problems, the architectural choices can be made on the basis of providing seemingly sufficient capacity by over-specifying the number of functions and terminals. Over-specification often works to provide the eventual architecture, at the expense of processing time and waste of resources.
Resources are used by each part of a program. The practical reality is that the amount of resources that one can afford to devote to a particular problem will strongly influence or dictate the architectural choice. Often the architectural choices are made on the basis of hoping that the resources that one could afford to devote to the problem will prove to be sufficient to solve the problem.
A retrospective analysis of the results of sets of actual runs made with various architectural choices can determine the optimal architectural choice for a given problem. That is, in retrospective analysis, a number of runs of the problem are made with different combinations of the number of functions and terminal to retrospectively compute the effort required to solve the problem with each such architecture and to identify the optimal architecture. If one is dealing with a number of related problems, a retrospective analysis of one problem may provide guidance for making the required architectural choice for a similar problem.
A computer program is an entity that receives inputs, performs computations, and produces outputs. A computer program performs basic arithmetic and conditional computations on.variables of various types (including integer, floating-point, and Boolean variables), performs iterations and recursions, stores intermediate results in memory, organizes groups of operations into reusable functions or subroutines, passes information to subroutines in the form of dummy variables (formal parameters), receives information from subroutines in the form of return values, and organizes subroutine and a main memory into a hierarchy. A system for automatically creating computer programs should create entities that possess most or all of the above essential features of computer programs.
What is needed is a process that allows architecture to be created automatically during the genetic process and that allows for the automatic allocation of resources based upon a set of fixed terminals and functions without user intervention.
U.S. Patents
U.S. Pat. No. 4,697,242, xe2x80x9cAdaptive Computing System Capable of Learning and Discoveryxe2x80x9d, issued Sep. 29, 1987, Holland et al.
U.S. Pat. No. 4,881,178, xe2x80x9cMethod of Controlling a Classifier System,xe2x80x9d issued Nov. 14, 1989, Holland et al.
U.S. Pat. No. 4,935,877, xe2x80x9cNon-Linear Genetic Algorithms for Solving Problems,xe2x80x9d issued Jun. 19, 1990, Koza.
U.S. Pat. No. 5,136,686, xe2x80x9cNon-Linear Genetic Algorithms for Solving Problems by Finding a Fit Composition of Functions,xe2x80x9d issued Aug. 4. 1992, Koza.
U.S. Pat. No. 5,148,513, xe2x80x9cA Non-Linear Genetic Process for Use with Plural Co-Evolving Populations,xe2x80x9d issued Sep. 15, 1992, Koza, John R., and Rice, James P.
U.S. Pat. No. 5,343,554, xe2x80x9cA Non-Linear Genetic Process for Data Encoding and for Solving Problems Using Automatically Defined Functions,xe2x80x9d issued Aug. 30, 1994, Koza, John R., and Rice, James P.
U.S. Pat. No. 5,742,738, xe2x80x9cSimultaneous Evolution of the Architecture of a Multi-part Program to Solve a Problem Using Architecture Altering Operations,xe2x80x9d issued Apr. 21, 1998, Koza, John R., Andre, David, and Tackett, Walter Alden.
U.S. Pat. No. 5,867,397, xe2x80x9cMethod and Apparatus for Automated Design of Complex Structures Using Genetic Programmingxe2x80x9d, issued Feb. 2, 1999, Koza, John R., Bennett III, Forrest H., and Andre, David.
Other Publications
Andre, David and Koza, John R., Evolution of map making: Learning, planning, and memory using genetic programming. Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE Press., Volume I, 1994.
Andre, David and Koza, John R., Parallel genetic programming: A scalable implementation using the transputer architecture. In Angeline, Peter J. and Kinnear, Kenneth E. Jr. (editors), 1996. Advances in Genetic Programming 2. Cambridge, Mass.: The MIT Press, 1996.
Brave, Scott, Using genetic programming to evolve mental models. Proceedings of the Fourth Golden West Conference on Intelligent Systems. Raleigh, N.C.: International Society for Computers and Their Applications, 1995.
Brave, Scott, The evolution of memory and mental models using genetic programming. In Koza, John R., Goldberg, David E., Fogel, David B., and Riolo, Rick L. (eds.). 1996. Genetic Programming 1996: Proceedings of the First Annual Conference, Jul. 28-31. 1996, Stanford University, Cambridge, Mass.: MIT Press, 1996.
Holland, John H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Ann Arbor, Mich.: University of Michigan Press. Second edition. Cambridge, Mass.: The MIT Press, 1975.
Holland, John H., Escaping brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems. In Michalski, Ryszard S., Carbonell, Jaime G. and Mitchell, Tom M. Machine Learning: An Artificial Intelligence Approach, Volume II. P. 593-623. Los Altos, Calif.: Morgan Kaufmann, 1986.
Koza, John R., Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, Mass.: The MIT Press, 1992.
Koza, John R., Genetic Programming II: Automatic Discovery of Reusable Programs. Cambridge, Mass.: The MIT Press, 1994.
Langdon, William B., Evolving data structures using genetic programming. In Eshelman, Larry J. (ed.). Proceedings of the Sixth International Conference on Genetic Algorithms. San Francisco, Calif.: Morgan Kaufmann Publishers, 1995.
Langdon, William B., Using data structures within genetic programming. In Koza, John R., Goldberg, David E., Fogel, David B., and Riolo, Rick L. (eds.), 1996. Genetic Programming 1996: Proceedings of the First Annual Conference. Jul. 28-31, 1996. Stanford University. Cambridge, Mass.: MIT Press, 1996.
Langdon, William B., Data structures and genetic programming. In Angeline, Peter J. and Kinnear, Kenneth E. Jr. (editors), 1996. Advances in Genetic Programming 2. Cambridge, Mass.: The MIT Press, 1996.
Langdon, William B., Genetic Programming and Data Structures: Genetic Programming+Data Structures=Automatic Programming! Amsterdam: Kluwer, 1998.
Nordin, Peter, A compiling genetic programming system that directly manipulates the machine code. In Kinnear, Kenneth E. Jr. (editor). Advances in Genetic Programming. Cambridge, Mass.: The MIT Press, 1994.
Raik, Simon E. and Browne, David G., Evolving state and memory in genetic programming. In Yao, Xin, Kim, J. H. and Furuhashi, T. (eds.). Simulated Evolution and Learning. First Asia-Pacific Conference SEAL ""96. Taejon, Korea, November 1996. Selected Papers. Lecture Notes in Artificial Intelligence, Volume 1285. Heidelberg: Springer-Verlag, 1997.
Teller, Astro, The evolution of mental models. In Kinnear, Kenneth E. Jr. (ed.). Advances in Genetic Programming. Cambridge, Mass.: The MIT Press, 1994.
Teller, Astro, Genetic programming, indexed memory, the halting problem, and other curiosities. Proceedings of the Seventh Florida Artificial Intelligence Research Symposium, 1994.
A general purpose genetic programming problem solving mechanism and process are described. In one embodiment, the computer programs are automatically generated to solve problems. In one embodiment, the process creates a population of programmatic entities from a set of generic functions. The process then generates a solution to the problem by altering an architecture of at least one programmatic entity in the population by performing at least one of an automatically defined loop, an automatically defined recursion, and an automatically defined store. The process then evolves the population to generate a new entity in the population.